#ifndef LINKLIST_H
#define LINKLIST_H
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <cstring>
#include <iomanip>

using namespace std;

typedef struct node{
    int data;
    struct node * next;
}list;

class LinkList
{
public:
    LinkList();
public:
    list * initSimpleLink()
    {
        list * head = (list*)malloc(sizeof (list));
        if(head == nullptr)
        {
            cout << "create fail!" <<  endl;
            exit(0);
        }
        head->next = nullptr;
        return head;
    }

    list * initCycleLink(int n)
    {
        int i = 0;
        list * head = nullptr, *cyclic = nullptr;
        head = (list*)malloc(sizeof(list));
        head->data = 1;
        head->next = nullptr;
        cyclic = head;
        for (i = 2; i <= n; i++) {
            list *body = (list*)malloc(sizeof (list));
            body->data = i;
            body->next = nullptr;
            cyclic->next = body;
            cyclic = cyclic->next;
        }
        cyclic->next = head;//首尾相连
        return head;
    }

    void findAndKillK(list * head, int k, int m)
    {
        list * p = nullptr;
        list * tail = head;
        //找到链表第一个结点的上一个结点，为删除操作做准备
        while(tail->next != head)
        {
            tail = tail->next;
        }

        p = head;
        //找到编号为k的人
        while(p->data != k)
        {
            tail = p;
            p = p->next;
        }
        //从编号为k的人开始，只有符合p->next==p时，说明链表中除了p结点，所有编号都出列了，
        while(p->next != p)
        {
            int i = 0;
            //找到从p报数1开始，报m的人，并且还要知道数m-1de人的位置tail，方便做删除操作。
            for (i = 1; i < m; i++) {
                tail = p;
                p = p->next;
            }

            tail->next = p->next;//从链表上将p结点摘下来
            cout << "出列人的编号为: "<< p->data << endl;
            free(p);
            p = tail->next;//继续使用p指针指向出列编号的下一个编号，游戏继续
        }
        cout << "出列人的编号为:" << p->data << endl;
        free(p);
    }

    /* 单链表反转 https://www.cnblogs.com/luego/p/11421590.html */
    list * reverseList(list * phead)
    {
        list * pnow = phead;
        list * ppre = nullptr;
        list * pnext = nullptr;
        list * newhead = nullptr;
        //开始遍历链表，若链表为空，返回NULL
        while(nullptr != pnow)
        {
            //若当前指针非NULL，则将pnext初始化为当前节点的下一个
            pnext = pnow->next;
            //链表只有一个元素，无需执行翻转操作
            if(nullptr == pnext)
            {
                newhead = pnow;
            }
            //当前节点指向前一个节点ppre
            pnow->next = ppre;
            //前一个节点ppre向后移动一个节点
            ppre = pnow;
            //当前节点pnow向后移动一个节点
            pnow = pnext;

        }
        cout << "reverse done!" << endl;

        return newhead;
    }
};

void testJosephusProbelm();

#endif // LINKLIST_H
